class Solution:
    def getMoneyAmount(self, n: int) -> int:
        dp = [[0 for i in range(n+2)] for j in range(n+2)]
        for i in range(n, 0, -1):
            for j in range(i, n+1):
                if i == j:
                    dp[i][j] = 0
                else:
                    dp[i][j] = float("inf")
                    for k in range(i, j+1):
                        dp[i][j] = min(dp[i][j], max(dp[i][k-1], dp[k+1][j]) + k)
        return dp[1][n]


# for i in range(1, 11):
#     print(i, i * (i-1) ** 2 / 20 + (i+11) * (10-i) ** 2 / 20)
a = Solution()
print(a.getMoneyAmount(10))
print(a.getMoneyAmount(1))
print(a.getMoneyAmount(2))
print(a.getMoneyAmount(3))
print(a.getMoneyAmount(4))
